//
//  Problem413.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 413. 等差数列划分
 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

 例如，以下数列为等差数列:
 1, 3, 5, 7, 9
 7, 7, 7, 7
 3, -1, -5, -9
 
 以下数列不是等差数列。
 1, 1, 2, 5, 7
  
 数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
 如果满足以下条件，则称子数组(P, Q)为等差数组：
 元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

 函数要返回数组 A 中所有为等差数组的子数组个数。

 示例:
     A = [1, 2, 3, 4]
     返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
 */
@objcMembers class Problem413: NSObject {
    func solution() {
        print(numberOfArithmeticSlices([1, 2, 3, 4]))
    }
    
    /*
     动态规划
     1: 创建一个二位数组 dp[len]
     2: dp[i]: 0 ~ i 为i为结尾的等差子数组个数
     3: dp[i] =
        3.1: [i-2 ~ i]是等差的话：存在2种情况：
            3.1.1 只有[i-2 ~ i](区间是3)是等差，那么 dp[i] = 1
            3.1.2 [i-3 ~ i](区间>3)是等差，那么dp[i-1]也是等差，dp[i] = dp[i-1] + 1, 因为增加1个
        3.2: [i-2 ~ i]不是等差，dp[i] = 0
     4: 求和
     */
    func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
        if nums.count < 3 {
            return 0
        }
        
        var dp = Array(repeating: 0, count: nums.count)
        
        var value = 0
        for i in 2..<nums.count {
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2] {   // 是等差序列
                // 2种情况：
                // 1: dp[i-1]也是等差序列 dp[i-1] > 0, + 1
                // 2: dp[i-1]不是等差学历 dp[i-1] = 0, + 1
                dp[i] = dp[i-1] + 1
            } else {
                dp[i] = 0
            }
            value += dp[i]
        }
        return value
    }
}
